Search Results

Documents authored by Downey, Rod

Found 3 Possible Name Variants:

Downey, Rod

Document
DOI: 10.4230/LIPIcs.STACS.2009.1810
Kolmogorov Complexity and Solovay Functions

Authors: Laurent Bienvenu and Rod Downey

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
Solovay (1975) proved that there exists a computable upper bound~$f$ of the prefix-free Kolmogorov complexity function~$K$ such that $f(x)=K(x)$ for infinitely many~$x$. In this paper, we consider the class of computable functions~$f$ such that $K(x) \leq f(x)+O(1)$ for all~$x$ and $f(x) \leq K(x)+O(1)$ for infinitely many~$x$, which we call Solovay functions. We show that Solovay functions present interesting connections with randomness notions such as Martin-L\"of randomness and K-triviality.
Cite as

Laurent Bienvenu and Rod Downey. Kolmogorov Complexity and Solovay Functions. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 147-158, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2009.1810,
  author =	{Bienvenu, Laurent and Downey, Rod},
  title =	{{Kolmogorov Complexity and Solovay Functions}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{147--158},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1810},
  URN =		{urn:nbn:de:0030-drops-18107},
  doi =		{10.4230/LIPIcs.STACS.2009.1810},
  annote =	{Keywords: Algorithmic randomness, Kolmogorov complexity, K-triviality}
}
Document
DOI: 10.4230/DagSemProc.07441.1
07441 Abstracts Collection – Algorithmic-Logical Theory of Infinite Structures

Authors: Rod Downey, Bakhadyr Khoussainov, Dietrich Kuske, Markus Lohrey, and Moshe Y. Vardi

Published in: Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)

Abstract
From 28.10. to 02.11.2007, the Dagstuhl Seminar 07441 ``Algorithmic-Logical Theory of Infinite Structures'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Rod Downey, Bakhadyr Khoussainov, Dietrich Kuske, Markus Lohrey, and Moshe Y. Vardi. 07441 Abstracts Collection – Algorithmic-Logical Theory of Infinite Structures. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{downey_et_al:DagSemProc.07441.1,
  author =	{Downey, Rod and Khoussainov, Bakhadyr and Kuske, Dietrich and Lohrey, Markus and Vardi, Moshe Y.},
  title =	{{07441 Abstracts Collection – Algorithmic-Logical Theory of Infinite Structures}},
  booktitle =	{Algorithmic-Logical Theory of Infinite Structures},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7441},
  editor =	{Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07441.1},
  URN =		{urn:nbn:de:0030-drops-14122},
  doi =		{10.4230/DagSemProc.07441.1},
  annote =	{Keywords: Theories of infinite structures , computable model theory and automatic structures , model checking infinite systems}
}
Document
DOI: 10.4230/DagSemProc.07441.2
07441 Summary – Algorithmic-Logical Theory of Infinite Structures

Authors: Rod Downey, Bakhadyr Khoussainov, Dietrich Kuske, Markus Lohrey, and Moshe Y. Vardi

Published in: Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)

Abstract
One of the important research fields of theoretical and applied computer science and mathematics is the study of algorithmic, logical and model theoretic properties of structures and their interactions. By a structure we mean typical objects that arise in computer science and mathematics such as data structures, programs, transition systems, graphs, large databases, XML documents, algebraic systems including groups, integers, fields, Boolean algebras and so on.
Cite as

Rod Downey, Bakhadyr Khoussainov, Dietrich Kuske, Markus Lohrey, and Moshe Y. Vardi. 07441 Summary – Algorithmic-Logical Theory of Infinite Structures. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{downey_et_al:DagSemProc.07441.2,
  author =	{Downey, Rod and Khoussainov, Bakhadyr and Kuske, Dietrich and Lohrey, Markus and Vardi, Moshe Y.},
  title =	{{07441 Summary – Algorithmic-Logical Theory of Infinite Structures}},
  booktitle =	{Algorithmic-Logical Theory of Infinite Structures},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7441},
  editor =	{Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07441.2},
  URN =		{urn:nbn:de:0030-drops-14111},
  doi =		{10.4230/DagSemProc.07441.2},
  annote =	{Keywords: Theories of infinite structures , computable model theory and automatic structures , model checking infinite systems}
}
Document
DOI: 10.4230/DagSemProc.05301.1
05301 Abstracts Collection – Exact Algorithms and Fixed-Parameter Tractability

Authors: Rod Downey, Martin Grohe, and Gerhard Woeginger

Published in: Dagstuhl Seminar Proceedings, Volume 5301, Exact Algorithms and Fixed-Parameter Tractability (2006)

Abstract
From 24.07.05 to 29.07.05, the Dagstuhl Seminar 05301 ``Exact Algorithms and Fixed-Parameter Tractability'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. This is a collection of abstracts of the presentations given during the seminar.
Cite as

Rod Downey, Martin Grohe, and Gerhard Woeginger. 05301 Abstracts Collection – Exact Algorithms and Fixed-Parameter Tractability. In Exact Algorithms and Fixed-Parameter Tractability. Dagstuhl Seminar Proceedings, Volume 5301, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{downey_et_al:DagSemProc.05301.1,
  author =	{Downey, Rod and Grohe, Martin and Woeginger, Gerhard},
  title =	{{05301 Abstracts Collection – Exact Algorithms and Fixed-Parameter Tractability}},
  booktitle =	{Exact Algorithms and Fixed-Parameter Tractability},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5301},
  editor =	{Rod Downey and Martin Grohe and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05301.1},
  URN =		{urn:nbn:de:0030-drops-4405},
  doi =		{10.4230/DagSemProc.05301.1},
  annote =	{Keywords: Fixed-parameter tractability, parameterized complexity, exact algorithms}
}
Document
DOI: 10.4230/DagSemProc.05301.2
05301 Summary – Exact Algorithms and Fixed-Parameter Tractability

Authors: Rod Downey, Martin Grohe, and Gerhard Woeginger

Published in: Dagstuhl Seminar Proceedings, Volume 5301, Exact Algorithms and Fixed-Parameter Tractability (2006)

Abstract
Summary of the Dagstuhl Seminar held 24. July - 29. July 2005.
Cite as

Rod Downey, Martin Grohe, and Gerhard Woeginger. 05301 Summary – Exact Algorithms and Fixed-Parameter Tractability. In Exact Algorithms and Fixed-Parameter Tractability. Dagstuhl Seminar Proceedings, Volume 5301, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{downey_et_al:DagSemProc.05301.2,
  author =	{Downey, Rod and Grohe, Martin and Woeginger, Gerhard},
  title =	{{05301 Summary – Exact Algorithms and Fixed-Parameter Tractability}},
  booktitle =	{Exact Algorithms and Fixed-Parameter Tractability},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5301},
  editor =	{Rod Downey and Martin Grohe and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05301.2},
  URN =		{urn:nbn:de:0030-drops-4396},
  doi =		{10.4230/DagSemProc.05301.2},
  annote =	{Keywords: Fixed-parameter tractability, parameterized complexity, exact algorithms}
}

Downey, Rodney

Document
DOI: 10.4230/LIPIcs.STACS.2018.15
On Low for Speed Oracles

Authors: Laurent Bienvenu and Rodney Downey

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
Relativizing computations of Turing machines to an oracle is a central concept in the theory of computation, both in complexity theory and in computability theory(!). Inspired by lowness notions from computability theory, Allender introduced the concept of "low for speed" oracles. An oracle A is low for speed if relativizing to A has essentially no effect on computational complexity, meaning that if a decidable language can be decided in time f(n) with access to oracle A, then it can be decided in time poly(f(n)) without any oracle. The existence of non-computable such A's was later proven by Bayer and Slaman, who even constructed a computably enumerable one, and exhibited a number of properties of these oracles as well as interesting connections with computability theory. In this paper, we pursue this line of research, answering the questions left by Bayer and Slaman and give further evidence that the structure of the class of low for speed oracles is a very rich one.
Cite as

Laurent Bienvenu and Rodney Downey. On Low for Speed Oracles. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2018.15,
  author =	{Bienvenu, Laurent and Downey, Rodney},
  title =	{{On Low for Speed Oracles}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{15:1--15:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.15},
  URN =		{urn:nbn:de:0030-drops-85226},
  doi =		{10.4230/LIPIcs.STACS.2018.15},
  annote =	{Keywords: Lowness for speed, Oracle computations, Turing degrees}
}
Document
DOI: 10.4230/DagRep.7.2.89
Computability Theory (Dagstuhl Seminar 17081)

Authors: Klaus Ambos-Spies, Vasco Brattka, Rodney Downey, and Steffen Lempp

Published in: Dagstuhl Reports, Volume 7, Issue 2 (2017)

Abstract
Computability is one of the fundamental notions of mathematics and computer science, trying to capture the effective content of mathematics and its applications. Computability Theory explores the frontiers and limits of effectiveness and algorithmic methods. It has its origins in Gödel's Incompleteness Theorems and the formalization of computability by Turing and others, which later led to the emergence of computer science as we know it today. Computability Theory is strongly connected to other areas of mathematics and theoretical computer science. The core of this theory is the analysis of relative computability and the induced degrees of unsolvability; its applications are mainly to Kolmogorov complexity and randomness as well as mathematical logic, analysis and algebra. Current research in computability theory stresses these applications and focuses on algorithmic randomness, computable analysis, computable model theory, and reverse mathematics (proof theory). Recent advances in these research directions have revealed some deep interactions not only among these areas but also with the core parts of computability theory. The goal of this Dagstuhl Seminar is to bring together researchers from all parts of computability theory and related areas in order to discuss advances in the individual areas and the interactions among those.
Cite as

Klaus Ambos-Spies, Vasco Brattka, Rodney Downey, and Steffen Lempp. Computability Theory (Dagstuhl Seminar 17081). In Dagstuhl Reports, Volume 7, Issue 2, pp. 89-101, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{ambosspies_et_al:DagRep.7.2.89,
  author =	{Ambos-Spies, Klaus and Brattka, Vasco and Downey, Rodney and Lempp, Steffen},
  title =	{{Computability Theory (Dagstuhl Seminar 17081)}},
  pages =	{89--101},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{2},
  editor =	{Ambos-Spies, Klaus and Brattka, Vasco and Downey, Rodney and Lempp, Steffen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.2.89},
  URN =		{urn:nbn:de:0030-drops-73540},
  doi =		{10.4230/DagRep.7.2.89},
  annote =	{Keywords: algorithmic randomness, computability theory, computable algebra, computable analysis, generic case complexity, proof mining}
}
Document
DOI: 10.4230/DagRep.2.1.19
Computability, Complexity and Randomness (Dagstuhl Seminar 12021)

Authors: Veronica Becher, Laurent Bienvenu, Rodney Downey, and Elvira Mayordomo

Published in: Dagstuhl Reports, Volume 2, Issue 1 (2012)

Abstract
Research on the notions of information and randomness has drawn on methods and ideas from computability theory and cumputational complexity, as well as core mathematical subjects like measure theory and information theory. The Dagstuhl seminar 12021 ``Computability, Complexity and Randomness'' was aimed to meet people and ideas in these areas to share new results and discuss open problems. This report collects the material presented during the course of the seminar.
Cite as

Veronica Becher, Laurent Bienvenu, Rodney Downey, and Elvira Mayordomo. Computability, Complexity and Randomness (Dagstuhl Seminar 12021). In Dagstuhl Reports, Volume 2, Issue 1, pp. 19-38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{becher_et_al:DagRep.2.1.19,
  author =	{Becher, Veronica and Bienvenu, Laurent and Downey, Rodney and Mayordomo, Elvira},
  title =	{{Computability, Complexity and Randomness (Dagstuhl Seminar 12021)}},
  pages =	{19--38},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{2},
  number =	{1},
  editor =	{Becher, Veronica and Bienvenu, Laurent and Downey, Rodney and Mayordomo, Elvira},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.1.19},
  URN =		{urn:nbn:de:0030-drops-34555},
  doi =		{10.4230/DagRep.2.1.19},
  annote =	{Keywords: algorithmic randomness, computability theory, computationl complexity, Kolmogorov complexity, algorithmic information theory}
}

Downey, Rodney G.

Document
DOI: 10.4230/DagSemRep.316
Parameterized Complexity (Dagstuhl Seminar 01311)

Authors: Rodney G. Downey, Michael R. Fellows, Rolf Niedermeier, and Peter Rossmanith

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Rodney G. Downey, Michael R. Fellows, Rolf Niedermeier, and Peter Rossmanith. Parameterized Complexity (Dagstuhl Seminar 01311). Dagstuhl Seminar Report 316, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{downey_et_al:DagSemRep.316,
  author =	{Downey, Rodney G. and Fellows, Michael R. and Niedermeier, Rolf and Rossmanith, Peter},
  title =	{{Parameterized Complexity (Dagstuhl Seminar 01311)}},
  pages =	{1--28},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{316},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.316},
  URN =		{urn:nbn:de:0030-drops-152009},
  doi =		{10.4230/DagSemRep.316},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact